#include"DynamicArray.h"
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>

struct DynamicArray
{
    ElementType *a; //数组指针
    int capacity; //数组容量
    int size;  //元素个数
};

struct Student
{
    int id;
    char *name;
};

DArray *InitDArry(int capacity)
{
    DArray *array= (DArray*)malloc(sizeof(DArray)); //先申请array动态复合数据类型指针 存储到堆上
    if(array== NULL)
    {
        printf("InitDArray malloc 申请失败\n");
        return NULL;
    }
    array->size=0;
    array->capacity= capacity;
    array->a= (ElementType *)malloc(sizeof(ElementType)*capacity);
    if(array->a== NULL)
    {
        printf("InitDArray malloc array申请失败\n");
        free(array);
        return NULL;
    }
    return array;
}

void InsertTail(DArray *array, ElementType element)
{
    if(array->size>= array->capacity)
    {
        array->capacity *= 2;
        ElementType*newPtr= realloc(array->a, sizeof(ElementType)*array->capacity);
        if(newPtr == NULL)
        {
            printf("扩容数组失败\n");
            array->capacity /= 2;
            return;
        }
        array->a = newPtr;
    }

    array->a[array->size++]= element; //合并 先赋值，size再++
}

void FreeDArray(DArray *array, void(*Free)(ElementType))
{
    for(int i=0; i<array->size; i++)
    {
        Free(array->a[i]);
    }
    free(array->a);
    free(array);
}

void PrintDArray(DArray *array, void (*print)(ElementType))
{
    printf("size: %d   capacity: %d\n",array->size,array->capacity);
    for(int i=0; i<array->size; i++)
    {
        print(array->a[i]);
    }
    printf("\n");
}

ElementType *FindByElement(DArray *array,ElementType element)
{
    //因为返回值需要表示很多意思，和NULL，所以使用指针
    for(int i=0; i<array->size; i++)
    {
        if(array->a[i]==element)
        return &array->a[i];
    }
    return NULL;
}

void RemoveByIndex(DArray *array,int index)
{
    if(index<0||index>=array->size)
    {
        printf("非法位置的删除\n");
        return;
    }

    for(int i= index; i< array->size; i++)
    {
        array->a[i]=array->a[i+1];
    }
}

void RemoveByElement(DArray *array, ElementType element)
{
    for(int i=0; i< array->size;i++)
    {
        if(array->a[i]==element) 
        {
            RemoveByIndex(array,i);
            array->size--;
            i--;
        }
    }
}

void FastSort(ElementType *a, int start, int end, bool(*Compare)(ElementType, ElementType))
{
    if(start>=end)
    return;

    int left= start;
    int right= end;
    ElementType temp= a[left]; //将最左边的值定位基准值
    while(left<right)
    {
        //右边往左动找比基准值小的数
        while (Compare(a[right],temp) && left<right)
        right--;
            
            if(left<right)
            {
            a[left]=a[right];
            left++;
            }   //把右边的比基准值小的数，扔到左边
        
        
        //左边往右边动找比基准值大的数
        while (Compare(temp,a[left]) && left<right)
        left++;
            
            if(left<right)
            a[right--]= a[left]; //把左边的比基准值大的数扔到右边
    }
                a[left]=temp;
            FastSort(a,start,left-1,Compare);
            FastSort(a,right+1,end,Compare);
}

void Sort(DArray *a, bool(*Compare)(ElementType, ElementType))
{
    FastSort(a->a,0,a->size-1,Compare);
}

Stu* BinarySearch(DArray*a, ElementType name,bool (*GreatName)(void *p1, void *p2),bool (*GreatName2)(void *p1, void *p2))
{
    int left=0;
    int right= a->size-1;
    while(left<=right)
    {
        int mid= left+(right-left)/2;
        // int mid= (left & right) + ((left ^ right)>>1);
    
    if(GreatName(a->a[mid],name))
        right= mid-1;

    else if(GreatName2(name,a->a[mid]))
        left= mid+1;

    else
        return a->a[mid];
    }
    return NULL;
}

Stu* Search(DArray *a, ElementType name)
{
    return BinarySearch(a, name, GreatName,GreatName2);
}


Stu* InitStu(int id, const char *name)
{
    Stu *s = (Stu *)malloc(sizeof(Stu));
    if(s==NULL)
    {
        printf("InitStu malloc error\n");
        return NULL;
    }
    s->id= id;
    // s->name = malloc(strlen(name)+1)  strcpy(s->name, name)
    s->name= strdup(name);  //在堆上拷贝出一个字符串:指针需要释放
    return s;
}

void FreeStu(void *ptr)
{
    Stu *s= (Stu *)ptr;
    free(s->name);   //双重数组先释放里面的元素
    free(s);
}

void printStu(void *str)
{
    Stu *s= (Stu *)str;
    printf("%d  %s\n",s->id,s->name);
}

bool CompareID(void *p1, void *p2)
{
    Stu *s1=(Stu *)p1;
    Stu *s2=(Stu *)p2;
    return s1->id>s2->id;
}

bool CompareName(void *p1, void *p2)
{
    Stu *s1=(Stu *)p1;
    Stu *s2=(Stu *)p2;
    return strcmp(s1->name,s2->name)>0;
}

bool GreatName(void *p1, void *p2)
{
    Stu *s1=(Stu *)p1;
    char *s2=(char *)p2;
    return strcmp(s1->name,s2)>0;
}

bool GreatName2(void *p1, void *p2)
{
    char *s1=(char *)p1;
    Stu *s2=(Stu *)p2;
    return strcmp(s1,s2->name)>0;
}
